{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Average Height of Buildings in Each Segment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: averageHeightOfBuildings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每段建筑物的平均高度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一条完全笔直的街道由一条数字线表示。街道上有建筑物，由二维整数阵列&nbsp;<code>buildings</code> 表示，其中 <code>buildings[i] = [start<sub>i</sub>, end<sub>i</sub>, height<sub>i</sub>]</code>。这意味着在 <strong>半封闭的位置</strong><code>[starti，endi]</code> 有一座高度为&nbsp;<code>height<sub>i</sub></code>&nbsp;的建筑。<br />\n",
    "你想用 <strong>最少</strong> 数量的非重叠 <strong>部分</strong> 来 <strong>描述</strong> 街道上建筑物的高度。街道可以用2D整数数组&nbsp;<code>street</code>&nbsp;来表示，其中&nbsp;<code>street[j] = [left<sub>j</sub>, right<sub>j</sub>, average<sub>j</sub>]</code>&nbsp;描述了道路的 <strong>半封闭区域</strong>&nbsp;<code>[left<sub>j</sub>, right<sub>j</sub>)</code>&nbsp;，该段中建筑物的 <strong>平均</strong> 高度为&nbsp;<code>average<sub>j</sub></code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果&nbsp;<code>buildings = [[1,5,2],[3,10,4]]</code>&nbsp;，&nbsp;<code>street = [[1,3,2],[3,5,3],[5,10,4]]</code>&nbsp;可以表示街道，因为：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>从 1 到 3 ，只有第一栋建筑的平均高度为 <code>2 / 1 = 2</code> 。</li>\n",
    "\t\t<li>从 3 到 5 ，第一和第二栋建筑的平均高度均为&nbsp;<code>（2+4） / 2 = 3 </code>。</li>\n",
    "\t\t<li>从 5 到 10 ，只有第二栋建筑的平均高度为 <code>4 / 1 = 4</code> 。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定&nbsp;<code>buildings</code> ，返回如上所述的二维整数矩阵<em>&nbsp;</em><code>street</code><em>&nbsp;</em>（ <strong>不包括</strong> 街道上没有建筑物的任何区域）。您可以按 <strong>任何顺序</strong> 返回数组。<br />\n",
    "<code>n</code> 个元素的 <strong>平均值</strong> 是 <code>n</code> 个元素除以&nbsp;<code>n</code> 的 <strong>总和</strong> （<strong>整数除法</strong>）。<br />\n",
    "<strong>半闭合段</strong>&nbsp;<code>[a, b)</code>&nbsp;是点&nbsp;<code>a</code>&nbsp;和 <code>b</code> 之间的数字线的截面，<strong>包括</strong> 点 <code>a</code> ，<strong>不包括&nbsp;</strong>点 <code>b</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例1：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/09/21/image-20210921224001-2.png\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> buildings = [[1,4,2],[3,9,4]]\n",
    "<strong>输出:</strong> [[1,3,2],[3,4,3],[4,9,4]]\n",
    "<strong>解释:</strong>\n",
    "从 1 到 3 ，只有第一栋建筑的平均高度为 2 / 1 = 2。\n",
    "从 3 到 4 ，第一和第二栋建筑的平均高度均为（2+4）/ 2 = 3。\n",
    "从 4 到 9 ，只有第二栋建筑的平均高度为 4 / 1 = 4。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> buildings = [[1,3,2],[2,5,3],[2,8,3]]\n",
    "<strong>输出:</strong> [[1,3,2],[3,8,3]]\n",
    "<strong>解释:</strong>\n",
    "从 1 到 2 ，只有第一栋建筑的平均高度为 2 / 1 = 2。\n",
    "从 2 到 3 ，这三座建筑的平均高度均为 （2+3+3） / 3 = 2。\n",
    "从 3 到 5 ，第二和第三栋楼都在那里，平均高度为 （3+3） / 2 = 3。\n",
    "从 5 到 8 ，只有最后一栋建筑的平均高度为 3 / 1 = 3。\n",
    "从 1 到 3 的平均高度是相同的，所以我们可以把它们分成一个部分。\n",
    "从 3 到 8 的平均高度是相同的，所以我们可以把它们分成一个部分。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> buildings = [[1,2,1],[5,6,1]]\n",
    "<strong>输出:</strong> [[1,2,1],[5,6,1]]\n",
    "<strong>解释:</strong>\n",
    "从 1 到 2 ，只有第一栋建筑的平均高度为 1 / 1 = 1。\n",
    "从 2 到 5 ，没有建筑物，因此不包括在输出中。\n",
    "从 5 到 6 ，只有第二栋建筑的平均高度为 1 / 1 = 1。\n",
    "我们无法将这些部分组合在一起，因为没有建筑的空白空间将这些部分隔开。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= buildings.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>buildings[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub> &lt; end<sub>i</sub> &lt;= 10<sup>8</sup></code></li>\n",
    "\t<li><code>1 &lt;= height<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [average-height-of-buildings-in-each-segment](https://leetcode.cn/problems/average-height-of-buildings-in-each-segment/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [average-height-of-buildings-in-each-segment](https://leetcode.cn/problems/average-height-of-buildings-in-each-segment/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,4,2],[3,9,4]]', '[[1,3,2],[2,5,3],[2,8,3]]', '[[1,2,1],[5,6,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        cf=defaultdict(int)\n",
    "        gs=defaultdict(int)\n",
    "        for s,e,h in buildings:\n",
    "            cf[s]+=h\n",
    "            cf[e]-=h \n",
    "            gs[s]+=1\n",
    "            gs[e]-=1\n",
    "        nk=list(cf.keys())\n",
    "        nk.sort()\n",
    "        res=[]\n",
    "        h,g=0,0\n",
    "        for i,j in pairwise(nk):\n",
    "            h+=cf[i]\n",
    "            g+=gs[i]\n",
    "            if g==0:continue\n",
    "            if res and i==res[-1][1] and h//g==res[-1][2]:\n",
    "                res[-1][1]=j\n",
    "            else:\n",
    "                res.append([i,j,h//g])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        diff = defaultdict(int)\n",
    "        cnts = defaultdict(int)\n",
    "        for a, b, h in buildings:\n",
    "            diff[a] += h\n",
    "            diff[b] -= h\n",
    "            cnts[a] += 1\n",
    "            cnts[b] -= 1\n",
    "        cur, cnt, last, last_p, ans = 0, 0, None, None, []\n",
    "        for k in sorted(diff.keys()):\n",
    "            cur += diff[k]\n",
    "            if last:\n",
    "                if ans and ans[-1][1] == last_p and ans[-1][2] == last // cnt:\n",
    "                    ans[-1][1] = k\n",
    "                else:\n",
    "                    ans.append([last_p, k, last // cnt])\n",
    "            cnt += cnts[k]\n",
    "            last, last_p = cur, k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        diff = defaultdict(int)\n",
    "        cnts = defaultdict(int)\n",
    "        for a, b, h in buildings:\n",
    "            diff[a] += h\n",
    "            diff[b] -= h\n",
    "            cnts[a] += 1\n",
    "            cnts[b] -= 1\n",
    "        cur, cnt, last, last_p, ans = 0, 0, None, None, []\n",
    "        for k in sorted(diff.keys()):\n",
    "            cur += diff[k]\n",
    "            if last:\n",
    "                if ans and ans[-1][1] == last_p and ans[-1][2] == last // cnt:\n",
    "                    ans[-1][1] = k\n",
    "                else:\n",
    "                    ans.append([last_p, k, last // cnt])\n",
    "            cnt += cnts[k]\n",
    "            last, last_p = cur, k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        diff = defaultdict(int)\n",
    "        cnts = defaultdict(int)\n",
    "        for a, b, h in buildings:\n",
    "            diff[a] += h\n",
    "            diff[b] -= h\n",
    "            cnts[a] += 1\n",
    "            cnts[b] -= 1\n",
    "        cur, cnt, last, last_p, ans = 0, 0, None, None, []\n",
    "        for k in sorted(diff.keys()):\n",
    "            cur += diff[k]\n",
    "            if last:\n",
    "                if ans and ans[-1][1] == last_p and ans[-1][2] == last // cnt:\n",
    "                    ans[-1][1] = k\n",
    "                else:\n",
    "                    ans.append([last_p, k, last // cnt])\n",
    "            cnt += cnts[k]\n",
    "            last, last_p = cur, k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        diff = defaultdict(int)\n",
    "        cnts = defaultdict(int)\n",
    "        # 建立差分数组和建筑计数\n",
    "        for a, b, h in buildings:\n",
    "            diff[a] += h\n",
    "            diff[b] -= h\n",
    "            cnts[a] += 1\n",
    "            cnts[b] -= 1\n",
    "        \n",
    "        cur, cnt, last, last_p, ans = 0, 0, None, None, []\n",
    "        # 对差分数组的键进行排序，然后按顺序处理\n",
    "        for k in sorted(diff.keys()):\n",
    "            cur += diff[k]\n",
    "            # 如果我们有一个有效的\"last\"值，这意味着我们有一个活动的建筑块\n",
    "            if last:\n",
    "                # 如果最后一个添加的块与当前块有相同的平均高度，则我们可以合并这两个块\n",
    "                if ans and ans[-1][1] == last_p and ans[-1][2] == last // cnt:\n",
    "                    ans[-1][1] = k\n",
    "                # 否则，我们添加一个新块\n",
    "                else:\n",
    "                    ans.append([last_p, k, last // cnt])\n",
    "            # 更新建筑数量\n",
    "            cnt += cnts[k]\n",
    "            # 设置\"last\"和\"last_p\"以供下次迭代使用\n",
    "            last, last_p = cur, k\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        sl = SortedList()\n",
    "        s0, cnt = 0, 0\n",
    "        ans = []\n",
    "        for l, r, x in buildings:\n",
    "            sl.add((l, x))\n",
    "            sl.add((r, -x))\n",
    "        p = -1\n",
    "        for x, y in sl:\n",
    "            if cnt: ans.append([p, x, s0 // cnt])\n",
    "            cnt += y // abs(y)\n",
    "            s0 += y\n",
    "            p = x\n",
    "        ans2 = []\n",
    "        for l, r, x in ans:\n",
    "            if l == r: continue\n",
    "            if not ans2: ans2.append([l, r, x])\n",
    "            else:\n",
    "                if ans2[-1][-1] == x and l == ans2[-1][1]:\n",
    "                    ans2[-1][1] = r\n",
    "                else:\n",
    "                    ans2.append([l, r, x])\n",
    "        return ans2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        points = set()\n",
    "        for x, y, _ in buildings:\n",
    "            points.add(x)\n",
    "            points.add(y)\n",
    "        points = sorted(list(points))\n",
    "        # 离散差分数组\n",
    "        h = defaultdict(int)\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y, w in buildings:\n",
    "            h[x] += w\n",
    "            h[y] -= w\n",
    "            cnt[x] += 1\n",
    "            cnt[y] -= 1\n",
    "        totH = totB = 0\n",
    "        for x, y in pairwise(points):\n",
    "            totH += h[x]\n",
    "            totB += cnt[x]\n",
    "            #print(totH, totB)\n",
    "            if totB > 0:\n",
    "                ans.append([x, y, totH // totB])\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "        ans2 = []\n",
    "        m = len(ans)\n",
    "        #print(ans)\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            j = i + 1\n",
    "            while j < m and ans[j][2] == ans[i][2] and ans[j][0] == ans[j - 1][1]:\n",
    "                j += 1\n",
    "            ans2.append([ans[i][0], ans[j - 1][1], ans[i][2]])\n",
    "            i = j\n",
    "        return ans2\n",
    "            \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
